package com.zrf.base.knowledge.collections;


import java.util.AbstractList;
import java.util.Arrays;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.RandomAccess;
import java.util.Spliterator;
import java.util.function.Consumer;

/**
 * 自己实现的arrayList
 *
 * @author zhouruifeng
 *         create at 2017/4/9.
 */
public class MyArrayList<T> extends AbstractList<T>
        implements List<T>, RandomAccess, Cloneable, java.io.Serializable {
    /**
     * 真实存储对象的数组
     */
    private transient Object[] elementData;
    /**
     * 对象的数组大小
     */
    private int size;

    /**
     * 指定数组的大小的构造方法
     *
     * @param initCapacity 初始化数组大小
     */
    public MyArrayList(int initCapacity) {
        if (initCapacity < 0) {
            throw new IllegalArgumentException("初始化数组大小不能为小于0");
        }
        this.elementData = new Object[initCapacity];
    }

    /**
     * 默认无参构造方法
     * 默认数组大小10个
     */
    public MyArrayList() {
        this(10);
    }

    public MyArrayList(Collection<? extends T> collection) {
        elementData = collection.toArray();
        size = elementData.length;
        //todo 这块不太懂
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

    private void checkDataSize(int needSize) {
        int curLength = elementData.length;
        if (needSize > curLength) {
            //数组扩容
            int newLength = curLength + (curLength >> 1);
            if (needSize > newLength) {
                newLength = needSize;
            }
            elementData = Arrays.copyOf(elementData, newLength);
        }
    }

    /**
     * 新增元素
     *
     * @param t 需要新增的元素
     * @return 成功或者失败
     */
    public boolean add(T t) {
        checkDataSize(size + 1);
        elementData[size++] = t;
        return true;
    }

    /**
     * 将元素插入制定位置
     *
     * @param index 需要插入的位置
     * @param t     元素
     */
    public void add(int index, T t) {
        checkIndexForAdd(index);
        checkDataSize(size + 1);
        //将制定位置元素后移
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        //设置制定位置元素
        elementData[index] = t;
        size++;
    }

    private void checkIndexForAdd(int index) {
        if (index > size || index < 0) {
            throw new IndexOutOfBoundsException(String.format("数组越界，大小:%d,index:%d", size, index));
        }
    }

    private void checkIndexForGetSet(int index) {
        if (index > size || index < 0) {
            throw new IndexOutOfBoundsException(String.format("数组越界，大小:%d,index:%d", size, index));
        }
    }

    /**
     * 将参数的数据添加到集合的尾部
     *
     * @param collection 需要添加的集合
     * @return 是否添加成功
     */
    public boolean addAll(Collection<? extends T> collection) {
        int needAddSize = collection.size();
        checkDataSize(size + needAddSize);
        //将数据添加到数据后面
        System.arraycopy(collection.toArray(), 0, elementData, size, needAddSize);
        size += needAddSize;

        return needAddSize != 0;
    }

    /**
     * 指定位置插入集合
     *
     * @param index      指定的位置
     * @param collection 需要插入的集合
     * @return 是否成功
     */
    public boolean addAll(int index, Collection<? extends T> collection) {
        checkIndexForAdd(index);
        int needInsertSize = collection.size();
        //检查数组大小
        checkDataSize(size + needInsertSize);
        //如果需要在中茶插入需要将数组后移
        if (index < size) {
            System.arraycopy(elementData, index, elementData, index + needInsertSize, size - index);
        }
        //将数组插入指定位置
        System.arraycopy(collection.toArray(), 0, elementData, index, needInsertSize);
        size += needInsertSize;
        return needInsertSize != 0;
    }

    /**
     * 设置指定位置的元素的值
     *
     * @param index 指定位置
     * @param t     设置的值
     * @return 之前的值
     */
    public T set(int index, T t) {
        checkIndexForGetSet(index);
        T oldValue = (T) elementData[index];
        elementData[index] = t;

        return oldValue;
    }

    /**
     * 得到指定位置的元素
     *
     * @param index 指定的位置
     * @return 指定位置的元素
     */
    public T get(int index) {
        checkIndexForGetSet(index);
        return (T) elementData[index];
    }

    /**
     * 移除指定位置的元素，并且后面的元素前移
     *
     * @param index 指定的位置
     * @return 之前的值
     */
    public T remove(int index) {
        checkIndexForGetSet(index);
        T oldValue = (T) elementData[index];

        if (index != size - 1) {
            System.arraycopy(elementData, index + 1, elementData, index, size - 1 - index);
        }
        elementData[--size] = null;
        return oldValue;
    }

    /**
     * 判断数组中的指定位置的元素是否与参数相等
     *
     * @param elementData 数组
     * @param index       指定位置
     * @param element     需要比较的元素
     * @return 是否相等
     */
    private boolean isEquals(Object[] elementData, int index, Object element) {
        return (element == null && elementData[index] == null) || (element != null && element.equals(elementData[index]));
    }

    /**
     * 移除指定元素
     *
     * @param obj 需要移除的元素
     * @return 是否存在
     */
    public boolean remove(Object obj) {
        int indexOf = indexOf(obj);
        if (indexOf >= 0) {
            remove(indexOf);
            return true;
        }
        return false;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

    @Override
    public Iterator<T> iterator() {
        return new MyIterator();
    }

    @Override
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

    @Override
    public <T1> T1[] toArray(T1[] a) {
        if (a.length < size) {
            return (T1[]) Arrays.copyOf(elementData, size, a.getClass());
        }

        System.arraycopy(elementData, 0, a, 0, size);
        return a;
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        if (c != null && !c.isEmpty()) {
            for (Object o : c) {
                if (!contains(o)) {
                    return false;
                }
            }
        }
        return true;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        if (c != null && !c.isEmpty()) {
            for (Object o : c) {
                remove(o);
            }
        }
        return true;
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        boolean isModified = false;
        Iterator<T> iterator = iterator();
        while (iterator.hasNext()) {
            if (!c.contains(iterator.next())) {
                iterator.remove();
                isModified = true;
            }
        }
        return isModified;
    }

    @Override
    public void clear() {
        for (int i = 0; i < size; i++) {
            elementData[i] = null;
        }
        size = 0;
    }

    @Override
    public int indexOf(Object o) {
        for (int i = 0; i < size; i++) {
            if (isEquals(elementData, i, o)) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public int lastIndexOf(Object o) {
        for (int i = size - 1; i >= 0; i--) {
            if (isEquals(elementData, i, o)) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public ListIterator<T> listIterator() {
        return new MyListIterator();
    }

    @Override
    public ListIterator<T> listIterator(int index) {
        return new MyListIterator(index);
    }

    @Override
    public List<T> subList(int fromIndex, int toIndex) {
        subListRangeCheck(fromIndex, toIndex, size);
        return new SubList(this, fromIndex, toIndex);
    }

    class SubList extends AbstractList<T> implements RandomAccess {
        /**
         * 最原始的list
         */
        private final AbstractList<T> realList;
        /**
         * 数组开始的index
         */
        private int fromIndex;
        /**
         * list可用的大小
         */
        private int size;

        SubList(AbstractList<T> list, int fromIndex, int endIndex) {
            this.realList = list;
            this.fromIndex = fromIndex;
            this.size = endIndex - fromIndex;
        }

        private void checkIndex(int index) {
            if (index > size || index < 0) {
                throw new IndexOutOfBoundsException(String.format("数组越界，大小:%d,index:%d", size, index));
            }
        }

        @Override
        public T get(int index) {
            checkIndex(index);
            return realList.get(fromIndex + index);
        }

        @Override
        public int size() {
            return size;
        }

        @Override
        public T set(int index, T e) {
            checkIndex(index);
            return realList.set(fromIndex + index, e);
        }

        public void add(int index, T e) {
            checkIndex(index);
            realList.add(fromIndex + index, e);
            this.size++;
        }

        public T remove(int index) {
            checkIndex(index);
            T result = realList.remove(fromIndex + index);
            this.size--;
            return result;
        }

        public boolean addAll(Collection<? extends T> c) {
            return addAll(this.size, c);
        }

        public boolean addAll(int index, Collection<? extends T> c) {
            rangeCheckForAdd(index);
            int cSize = c.size();
            if (cSize == 0) {
                return false;
            }

            realList.addAll(fromIndex + index, c);
            this.size += cSize;
            return true;
        }

        public Iterator<T> iterator() {
            return listIterator();
        }

        public ListIterator<T> listIterator(final int index) {
            rangeCheckForAdd(index);
            final int offset = this.fromIndex;

            return new ListIterator<T>() {
                int cursor = index;
                int lastRet = -1;

                public boolean hasNext() {
                    return cursor != MyArrayList.SubList.this.size;
                }

                public T next() {
                    int i = cursor;
                    if (i >= MyArrayList.SubList.this.size)
                        throw new NoSuchElementException();
                    Object[] elementData = MyArrayList.this.elementData;
                    if (offset + i >= elementData.length)
                        throw new ConcurrentModificationException();
                    cursor = i + 1;
                    return (T) elementData[offset + (lastRet = i)];
                }

                public boolean hasPrevious() {
                    return cursor != 0;
                }

                public T previous() {
                    int i = cursor - 1;
                    if (i < 0)
                        throw new NoSuchElementException();
                    Object[] elementData = MyArrayList.this.elementData;
                    if (offset + i >= elementData.length)
                        throw new ConcurrentModificationException();
                    cursor = i;
                    return (T) elementData[offset + (lastRet = i)];
                }

                public void forEachRemaining(Consumer<? super T> consumer) {
                    Objects.requireNonNull(consumer);
                    final int size = MyArrayList.SubList.this.size;
                    int i = cursor;
                    if (i >= size) {
                        return;
                    }
                    final Object[] elementData = MyArrayList.this.elementData;
                    if (offset + i >= elementData.length) {
                        throw new ConcurrentModificationException();
                    }
                    while (i != size) {
                        consumer.accept((T) elementData[offset + (i++)]);
                    }
                    // update once at end of iteration to reduce heap write traffic
                    lastRet = cursor = i;
                }

                public int nextIndex() {
                    return cursor;
                }

                public int previousIndex() {
                    return cursor - 1;
                }

                public void remove() {
                    if (lastRet < 0) {
                        throw new IllegalStateException();
                    }

                    try {
                        MyArrayList.SubList.this.remove(lastRet);
                        cursor = lastRet;
                        lastRet = -1;
                    } catch (IndexOutOfBoundsException ex) {
                        throw new ConcurrentModificationException();
                    }
                }

                public void set(T e) {
                    if (lastRet < 0) {
                        throw new IllegalStateException();
                    }

                    try {
                        MyArrayList.this.set(offset + lastRet, e);
                    } catch (IndexOutOfBoundsException ex) {
                        throw new ConcurrentModificationException();
                    }
                }

                public void add(T e) {

                    try {
                        int i = cursor;
                        MyArrayList.SubList.this.add(i, e);
                        cursor = i + 1;
                        lastRet = -1;
                    } catch (IndexOutOfBoundsException ex) {
                        throw new ConcurrentModificationException();
                    }
                }
            };
        }

        public List<T> subList(int fromIndex, int toIndex) {
            subListRangeCheck(fromIndex, toIndex, size);
            return new MyArrayList.SubList(this, fromIndex, toIndex);
        }

        private void rangeCheckForAdd(int index) {
            if (index < 0 || index > this.size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }

        protected void removeRange(int fromIndex, int toIndex) {
            ListIterator<T> it = listIterator(fromIndex);
            for (int i = 0, n = toIndex - fromIndex; i < n; i++) {
                it.next();
                it.remove();
            }
            this.size -= toIndex - fromIndex;
        }

        private String outOfBoundsMsg(int index) {
            return "Index: " + index + ", Size: " + this.size;
        }

        public Spliterator<T> spliterator() {
            return null;
        }

    }

    /**
     * 检查参数是否异常
     *
     * @param fromIndex 开始的index
     * @param toIndex   结束的index
     * @param size      数组的大小
     */
    static void subListRangeCheck(int fromIndex, int toIndex, int size) {
        if (fromIndex < 0) {
            throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
        }
        if (toIndex > size) {
            throw new IndexOutOfBoundsException("toIndex = " + toIndex);
        }
        if (fromIndex > toIndex) {
            throw new IllegalArgumentException("fromIndex(" + fromIndex +
                    ") > toIndex(" + toIndex + ")");
        }
    }

    class MyIterator implements Iterator<T> {
        /**
         * 游标
         */
        private int cursor;

        @Override
        public boolean hasNext() {
            return cursor < size;
        }

        @Override
        public T next() {
            if (cursor >= size) {
                throw new NoSuchElementException();
            }
            return (T) elementData[cursor++];
        }

        @Override
        public void remove() {
            if (cursor - 1 < 0) {
                throw new IllegalStateException();
            }
            MyArrayList.this.remove(--cursor);
        }

        @Override
        public void forEachRemaining(Consumer<? super T> action) {
            Objects.requireNonNull(action);
            if (cursor >= size) {
                return;
            }
            while (cursor != size) {
                action.accept((T) elementData[cursor++]);
            }
        }
    }

    /**
     * 自己实现的list iteraotr
     */
    class MyListIterator implements ListIterator<T> {
        /**
         * 当前的数组的游标
         */
        private int cursor;

        /**
         * 指定index的构造方法
         *
         * @param index 指定位置
         */
        MyListIterator(int index) {
            this.cursor = index;
        }

        MyListIterator() {

        }

        @Override
        public boolean hasNext() {
            return cursor < size;
        }

        @Override
        public T next() {
            return (T) elementData[cursor++];
        }

        @Override
        public boolean hasPrevious() {
            return cursor > 0;
        }

        @Override
        public T previous() {
            return (T) elementData[--cursor];
        }

        @Override
        public int nextIndex() {
            return cursor;
        }

        @Override
        public int previousIndex() {
            return cursor - 1;
        }

        @Override
        public void remove() {
            cursor--;
            MyArrayList.this.remove(cursor);
        }

        @Override
        public void set(T t) {
            elementData[cursor - 1] = t;
        }

        @Override
        public void add(T t) {
            MyArrayList.this.add(cursor, t);
        }
    }
}
